問題

這邊一樣以 AtCoder Educational DP Contest 的類題來舉例，這題是 C - Vacation，題意簡單來說就是每天都可以進行一種運動，做每種運動都會有自己所獲得的快樂指數，然後有一個限制條件是當天不可以跟前一天做一樣的運動，問第 ~ 天可以獲得的最大快樂值是多少

解題思路

每一天都不可以跟前一天是相同的運動，所以可以從前一天做的不同運動選取到那一天最大的快樂值然後再加上當天的快樂值，然後到第 天就選三種運動中最大的那一個快樂值

AC Code

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long n;
    cin >> n;
    vector<long long> a(n),b(n),c(n);
    for(int i = 0;i < n;i++){
    	cin >> a[i] >> b[i] >> c[i];
    }
    vector<vector<long long>> dp(n,vector<long long>(3,-1));
    dp[0][0] = a[0],dp[0][1] = b[0],dp[0][2] = c[0];
    for(int i = 1;i < n;i++){
    	dp[i][0] = max(dp[i - 1][1],dp[i - 1][2]) + a[i];
    	dp[i][1] = max(dp[i - 1][0],dp[i - 1][2]) + b[i];
    	dp[i][2] = max(dp[i - 1][1],dp[i - 1][0]) + c[i];
    }
    cout << max({dp[n - 1][0],dp[n - 1][1],dp[n - 1][2]}) << "\n";
    return 0;
}

時間複雜度

因為只需要遍歷一次陣列，陣列大小為 ，所以時間複雜度是

總結

今天的題目不太算是經典題，不過他算是競賽可能出現的簡單 DP，因為是比較直觀的題目，所以可以訓練自己思考這些簡單的 DP 題，再往更難的題目思考，因為這種不定型的題目算是非常吃自己的解題邏輯和思路的

預告

明天是最後一天講解題目了，預計會是背包問題，一樣會用 AtCoder Educational DP Contest，的題目來講，大家可以先看看